Introduction to DFA
Introduction to DFA continued
NFA with epsilon moves to NFA without epsilon moves
Problem discussion
Problems continued
Regular expression to DFA with epsilon moves
DFA to regular expression
Closure properties of regular sets
Minimization of finite automata
Problems on minimization
Introduction to CFG
Regular grammar
Ambigous grammar
Elimination of useless symbols
Elimination of epsilon and unit productions
CYK Algorithm
S-Grammar
Closure properties of context free languages
Pumping lemma for regular languages
Problems on Pumping lemma for regular languages
Problem solving
Push down Automaton
Deterministic and Non-deterministic PDA
Push down Automaton and Context free languages
PDA to CFL conversion
Problem solving
Turing machine
Designing a Turing machine for accepting a language
Designing a Turing machine for addition
Designing a Turing machine to multiply two positive integers
Chomsky Hierarchy
Primitive Recursive functions
Primitive Recursive functions(cont)
Polynomial time reduction
Recursive and recursively enumerable languages.
Unrestricted grammarand context sensitive grammar
Satisfiability problem
Homomorphism
P,NP and NP complete
NP complete problems
Turing machine for multiplication
Theorem proving